package leetcode.other.p2561;

import java.util.*;

class Solution {
    public long minCost(int[] basket1, int[] basket2) {
        Map<Integer, Integer> counter = new HashMap<>();
        for (int i = 0; i < basket1.length; i++) {
            counter.merge(basket1[i], 1, Integer::sum);
            counter.merge(basket2[i], -1, Integer::sum);
        }
        List<Integer> a = new ArrayList<>();
        List<Integer> b = new ArrayList<>();
        int mn = Integer.MAX_VALUE;
        for (Map.Entry<Integer, Integer> entry : counter.entrySet()) {
            int k = entry.getKey();
            int v = entry.getValue();
            if (v % 2 != 0) {
                return -1;
            }
            mn = Math.min(mn, k);
            if (v > 0) {
                for (int i = 0; i < v / 2; i++) {
                    a.add(k);
                }
            } else if (v < 0) {
                for (int i = 0; i < -v / 2; i++) {
                    b.add(k);
                }
            }
        }

        a.sort(Comparator.comparingInt(o -> o));
        b.sort(Collections.reverseOrder());
        long minCost = 0;
        for (int i = 0; i < a.size(); i++) {
            minCost += Math.min(Math.min(a.get(i), b.get(i)), mn * 2);
        }
        return minCost;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().minCost(new int[]{4, 2, 2, 2}, new int[]{1, 4, 1, 2}));
        System.out.println(new Solution().minCost(new int[]{2, 3, 4, 1}, new int[]{3, 2, 5, 1}));
        System.out.println(new Solution().minCost(new int[]{4, 4, 4, 4, 3}, new int[]{5, 5, 5, 5, 3}));
    }
}